REMitW - Step 1: パースする
初期の頃、正規表現の構文は非常にシンプルで、最初の記事で説明した簡単な概念、すなわち連結、繰り返し、および選択を模倣していました。キャラクタクラス、+および?演算子、位置指定子の^および$など、装飾的な機能はほとんどありませんでした。今日では、プログラマーは多くの装飾的な機能を期待しています。現代の正規表現パーサーの仕事は、この騒音の中から意味を見出し、元の基本的な概念に戻していくことです。RE2のパーサーは、regexp.hで定義されたRegexpデータ構造を作成します。これは、いくつかの特別なケースを除いて、元のegrep構文に非常に近いものです:
リテラル文字列は、個々のkRegexpLiteralノードを連結するよりもメモリを少なく消費するkRegexpLiteralStringノードで表されます。
数えられた繰り返しはkRegexpRepeatノードで表されますが、その表現は直接実装することはできません。これらが後でどのようにコンパイルされるかを見ていきます。
キャラクタクラスは、単純な範囲のリストやビットマップとしてではなく、範囲のバランスの取れた二分木として表されます。この表現は単純なリストよりも複雑ですが、大きなUnicodeキャラクタクラスを処理するためには重要です。
「任意の文字」キャラクタクラスや「任意のバイト」演算子には特別なノードタイプが割り当てられます。これは、UTF-8入力テキストをマッチングするときに(RE2のデフォルト動作モード)、両者の間に違いが生じるためです。
ケースインセンシティブなマッチングは、ASCII範囲に対して特別なフラグとケースを使用し、2要素のキャラクタクラスではなくなります:(?i)abcは、AaBbCcではなく、大文字小文字区別なしのビットを持つabcに変わります。RE2は元々後者を使用していましたが、特に木構造のキャラクタクラスではメモリ集約的すぎました。 RE2のパーサーはparse.ccにあります。これは手書きのパーサーであり、特定のパーサージェネレータに依存することを避けるため、また現代の正規表現構文が不規則で特別な注意を要するためです。パーサーは再帰的下降を使用せず、再帰深度が潜在的に無制限であり、特にスレッド環境ではスタックオーバーフローの可能性があるためです。代わりに、パーサーは生成されたLR(1)パーサーのように、明示的な解析スタックを維持します。
私が驚いたことの一つは、実際のユーザーが同じ正規表現をさまざまな方法で書くことです。例えば、エスケープの代わりにシングルトンキャラクタクラスを使用することが一般的です—. instead of .—またはキャラクタクラスの代わりに選択を使用—a|b|c|d instead of a-d。パーサーはこれらの最も効率的な形式を使用するよう特別に注意し、.は単一のリテラル文字、a|b|c|dはキャラクタクラスとして扱われます。これらの簡略化は、解析中に行い、二次パスで行うのではなく、不必要に大きな中間メモリフットプリントを避けるためです。 現代の多機能な「正規表現」から、初期のシンプルな(連結、繰り返し、代替のみからなる)正規表現に戻すことが現代の正規表現パーサーの仕事になる
RE2のパーサーはregexp.hで定義されたRegexpの値を作る Regexpはegrepの構文に似ている。
異なる点は次のとおり
用語